package com.aug_leo.datastructure.linkedlist;


/**
 * 共尾链表
 */
public class Ex2Leetcode160 {

    /*
        思路: 称两个链表为 a=[1, 2, 4, 5]，b=[3, 4, 5]，图中用 N 代表 null
            1.遍历 a，遇到 null 时改道遍历 b
            2.与此同时，遍历 b，遇到 null 时改道遍历 a
            3.在此过程中，如果 遇到相同 的节点，即为找寻目标，返回即可，如下图中的第二次出现的 4
            4.相同节点应该比较其 引用值，图中数字只是为了便于区分

            1	2	4	5	N	3	4	5	N
            3	4	5	N	1	2	4	5	N

            如果两个链表长度相同，则可以更早找到目标，例如 a=[1, 4, 5]，b=[3, 4, 5]，第一次出现 4 时，即可返回
            1	4	5	N	3	4	5	N
            3	4	5	N	1	4	5	N

            如果是非共尾的情况，如 a=[1, 2, 4]，b=[3, 5]，可以看到，唯一相等的情况，是遍历到最后那个 N 此时退出循环
            1	2	4	N	3	5	N
            3	5	N	1	2	4	N
     */

    /**
     * 获取两个链表的交点节点
     * 如果两个链表有交点，则返回交点节点；如果没有交点，则返回null
     *
     * @param headA 第一个链表的头节点
     * @param headB 第二个链表的头节点
     * @return 交点节点或null
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 初始化两个指针，分别指向两个链表的头节点
        ListNode pointer1 = headA;
        ListNode pointer2 = headB;
        // 循环直到找到交点节点
        while (true) {
            // 如果两个指针指向同一个节点，则该节点为交点节点
            if (pointer1 == pointer2) {
                return pointer1;
            }

            // 如果指针1到达链表末尾，则将其重置为链表2的头节点，继续循环
            if (pointer1 == null) {
                pointer1 = headB;
            } else {
                // 否者指针 pointer1 移动到下一个节点
                pointer1 = pointer1.next;
            }

            // 如果指针2到达链表末尾，则将其重置为链表1的头节点，继续循环
            if (pointer2 == null) {
                pointer2 = headA;
            } else {
                // 否则，将指针 pointer2 移动到下一个节点
                pointer2 = pointer2.next;
            }
        }
    }


    public static void main(String[] args) {
//        ListNode c = ListNode.of(4, 5);
//        ListNode a = ListNode.of(1, 2).append(c);
//        ListNode b = ListNode.of(3).append(c);

        ListNode c = ListNode.of(1);
        ListNode a = c;
        ListNode b = c;

        System.out.println(new Ex2Leetcode160().getIntersectionNode(a, b));
    }
}
